1. Field of the Invention
The present invention relates to the design of real-time distributed embedded systems, and, in particular, to the process of partitioning an embedded system specification into hardware and software modules using hardware-software co-synthesis.
2. Description of the Related Art
Embedded systems have begun to play a significant role in our day-to-day lives. Fault-tolerant distributed embedded systems can offer high performance as well as reliability and availability to meet the needs of critical real-time applications. Many embedded systems concurrently perform a multitude of complex tasks. Heterogeneous distributed architectures are commonly used to meet the performance needs for such systems. These architectures contain several general-purpose processors and application-specific integrated circuits (ASICs) of different types which are interconnected by various types of communication links. Each task to be performed on the system can be executed on a variety of software and hardware modules which have different dollar costs, reliability, area, delay, and power requirements. For example, a task can be performed on a general-purpose processor (software) or an ASIC (hardware). Similarly, a message can be communicated via a serial link, local area network (LAN), or a bus. Parameters such as area, delay, reliability, and power are usually estimated by simulation/synthesis or laboratory measurement from previous designs.
The derivation of an optimal hardware-software architecture requires selection of processors, ASICs, and communication links such that all real-time, reliability, and availability constraints are met and the architecture cost is minimum. The key steps of hardware-software co-synthesis are: a) allocation, b) scheduling, and c) performance estimation. The allocation step identifies mapping of tasks to processing elements (PEs) and inter-task communications to communication links. The scheduling step determines the order of execution of tasks and edges on PEs and links, respectively. The performance estimation step estimates the finish time of each task and determines the overall quality of the system in terms of its dollar cost, fault tolerance, reliability, availability, etc. Both allocation and scheduling are known to be NP-complete. See References (1)-(2). Therefore, optimal co-synthesis is a computationally hard problem.
Research on hardware-software co-synthesis is fairly recent and its primary focus has been on one-CPU-one-ASIC architectures. See References (3)-(8). Distributed embedded system architectures can employ multiple processors, ASICs, and field-programmable gate arrays (FPGAs). See Reference (9). Optimal (see References (10)-(11)) and heuristic (see References (12)-(16)) are two major approaches to solve the distributed system co-synthesis problem. Mixed integer linear programming (MILP) and exhaustive are two distinct optimal approaches. Prakash and Parker have proposed MILP-based co-synthesis (see Reference (10)) which has the following limitations: 1) it allows only one task graph, 2) it does not allow preemptive scheduling, 3) it requires specifications of interconnection topology up front, and 4) it does not consider fault tolerance. Due to computational complexity, it is only suitable for small task graphs consisting of about 10 tasks. Ambrosio and Hu have proposed a configuration-level hardware-software partitioning algorithm (see Reference (11)) which is based on an exhaustive enumeration of all possible solutions. Limitations of this approach are: 1) it allows an architecture with at most one CPU and few ASICs, 2) it ignores communication overheads, 3) it does not consider fault tolerance, and 4) it uses simulation for performance evaluation which is very time-consuming.
Iterative (see References (12)-(14)) and constructive (see References (15)-(16)) are two distinct approaches in the heuristic domain. In the iterative approach, an initial solution is iteratively improved through various architecture moves. In the constructive approach, the architecture is built step-by-step and the complete architecture is not available before completion of the algorithm. The iterative procedures given in References (12)-(13) do not address fault tolerance and consider only one type of communication link. They do not allow mapping of successive instances of a periodic task to different PEs, which may be important in deriving cost-effective architectures. The algorithm in Reference (14) employs power dissipation as a cost function for allocation. It ignores inter-task communication scheduling. A constructive co-synthesis algorithm for fault-tolerant distributed embedded systems has been proposed in Reference (15). The method in Reference (15) has the following limitations: 1) it employs task-based fault tolerance (TBFT) (see Reference (17)), but does not exploit the error transparency property (explained later) which can significantly reduce the fault tolerance overhead, 2) it does not support communication topologies such as bus, LAN, etc., 3) it employs a pessimistic finish time estimation technique which may increase the architecture cost, 4) it does not address availability of systems, and 5) it is not suitable for multirate systems. The primary focus in Reference (16) is on general and low-power co-synthesis of distributed embedded systems. The methods in Refierences (18)-(21) consider fault tolerance during task allocation, but not during co-synthesis. Direct optimization of dependability (reliability and availability) or determination of an efficient error recovery topology of the architecture has not been attempted before during co-synthesis. Also, the concepts of multidimensional assertions and assertion sharing have not been exploited before.